package com.wuxuan.algorithm_homework.pathMerge;

import com.wuxuan.algorithm_homework.linkedList.LinkedListProblems;

import java.util.*;

/**
 * 多路归并
 * <p>
 * 合并 K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表示例 1:
 * 输入:lists =[[1,4,5],[1,3,4][2,6]]
 * 输出:[1, 1, 2, 3, 4, 4, 5, 6]
 */
public class MergeKLists {
    class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        //准备工作
        if (lists == null || lists.length == 0) {
            return null;
        }

        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;


        //1.先创建一个 小顶堆(优先队列)
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.value - o2.value;
            }
        });

        //2.将K的链表的头节点加入到堆里面
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        //3.将堆顶的元素取出并合并到主链表，并且将链表的下一个元素加入堆4.重复3，直到堆中的所有元素都加入到主链表
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }
        //5.返回主链表的头节点
        return dummyNode.next;
    }

    private ListNode arrayToLinkedList(int[] a) {
        if (a == null || a.length == 0) {
            return null;
        }

        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        for (int ele : a) {
            cur.next = new ListNode(ele);
            cur = cur.next;
        }
        return dummyNode.next;
    }

    private void printLinkedList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.value + " -> ");
            cur = cur.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        MergeKLists test = new MergeKLists();
        int[] a1 = {1, 4, 5};
        int[] a2 = {1, 3, 4};
        int[] a3 = {2, 6};
        ListNode node1 = test.arrayToLinkedList(a1);
        ListNode node2 = test.arrayToLinkedList(a2);
        ListNode node3 = test.arrayToLinkedList(a3);
        test.printLinkedList(node1);
        test.printLinkedList(node2);
        test.printLinkedList(node3);

        ListNode mergeNode = test.mergeKLists(new ListNode[]{node1, node2, node3});
        test.printLinkedList(mergeNode);
    }

}
